package com.tim.test.leetcode;

import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.TypeReference;
import org.junit.Test;

import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;
import java.util.stream.Collectors;

/**
 * @author
 * @Title:
 * @Package
 * @date 2023/6/5 21:26
 * @Description:
 */
public class Answer {
    public static void main(String[] args) {
        Answer answer = new Answer();
        Object r;
//      r = answer.lengthOfLongestSubstring("tmmzuxt");
//        int[] integers = new int[]{1, 0, -1, 0, -2, 2};
//      r =   answer.fourSum(integers, 0);

//      r =   answer.longestPalindrome("ccc");
//      r =   answer.checkRecord("PPALLL");
        r = answer.findSubsequences(new int[]{1,2,3,4,5,6,7,8,9,10,1,1,1,1,1});

        System.out.println(JSON.toJSONString(r));
    }


    /**
     *003
     *  向右探索；若字符存在，则更新start，不存在则计算maxLen
     *  更新start时，移除val<start的key
     *  子串-滑动窗口，Map定位
     */
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        if(len==0){
            return 0;
        }
        int start=0, maxLen=1;
        Map<Character, Integer> map = new HashMap<>();
        map.put(s.charAt(start), start);
        for(int i=1; i<len; i++){
            char targetChar = s.charAt(i);
            if(map.containsKey(targetChar) && map.get(targetChar)>=start){
                start = map.get(targetChar)+1;
                map.put(targetChar, i);
            }else{
                map.put(targetChar, i);
                maxLen = Math.max(maxLen, i-start+1);
            }
        }
        return maxLen;
    }


    /**
     *018
     *  参照两数之和，放Map判定
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        int len = nums.length;
        if(len<4){
            return Collections.emptyList();
        }
        Arrays.sort(nums);
        for(int i=0; i<len; i++){
            int val = nums[i];
            if(!map.containsKey(val)){
                map.put(val, new ArrayList<>());
            }
            map.get(val).add(i);
        }
        if(target/4<nums[0]-1 || target/4>nums[nums.length-1]+1){
            return Collections.emptyList();
        }
        List<List<Integer>> result = new ArrayList<>();
        Set<String> set = new HashSet<>();
        for(Integer key : map.keySet()){
            if(key<nums[3]){
                continue;
            }
            for (int i = 0; i < len; i++) {
                if(i>0 && nums[i]==nums[i-1]){
                    continue;
                }
                if(nums[i]>key){
                    continue;
                }
                for (int j = i+1; j < len; j++) {
                    if(j>i+1 && nums[j]==nums[j-1]){
                        continue;
                    }
                    for (int k = j+1; k < len; k++) {
                        if(k>j+1 && nums[k]==nums[k-1]){
                            continue;
                        }
                        if((long)key == ((long)target)-nums[i]-nums[j]-nums[k]){
                            List<Integer> vals = map.get(key);
                            for(Integer val :vals){
                                if(k<val){
                                    List<Integer> e = Arrays.asList(nums[i], nums[j], nums[k], nums[val]);
                                    Collections.sort(e);
                                    String s = e.stream().map(Objects::toString).collect(Collectors.joining(","));
                                    if(!set.contains(s)){
                                        set.add(s);
                                        result.add(e);
                                        break;
                                    }
                                }
                            }
                        }
                    }
                }
            }


        }return result;
    }

    /**
     * 005
     *  cs[i]=cs[i+1]时，滑动窗口比较，记录最大值
     */
    public String longestPalindrome(String s) {
        int length = s.length();
        if(length<2){
            return s;
        }
        char[] chars = s.toCharArray();
        int left=0, right=0;
        for (int i =0; i < length-1; i++) {
            if(chars[i]==chars[i+1]){// 对称
                int start=i, end=i+1;
                while(start-1>-1 && end+1<length && chars[start-1]==chars[end+1]){
                    start=start-1;
                    end=end+1;
                }
                if(end-start>right-left){
                    left=start;
                    right=end;
                }
            }
            if(i>0 && chars[i-1]==chars[i+1]){// 中间
                int start=i-1, end=i+1;
                while(start-1>-1 && end+1<length && chars[start-1]==chars[end+1]){
                    start=start-1;
                    end=end+1;
                }
                if(end-start>right-left){
                    left=start;
                    right=end;
                }
            }
        }
        return s.substring(left, right+1);

    }

    /**
     * 551
     *  遍历判断
     */
    public boolean checkRecord(String s) {
        int length = s.length();
        if(length<2){
            return true;
        }
        s = s.toUpperCase();
        char[] chars = s.toCharArray();
        int times = 0;
        for (int i =0; i < length; i++) {
            char aChar = chars[i];
            if('A'==aChar){
                times++;
                if(times>1){
                    return false;
                }
            }else if('L'==aChar){
                int j=0;
                while(i+j+1<length && 'L'==chars[i+j+1]){
                    j++;
                    if(j>1){
                        return false;
                    }
                }
            }
        }
        return true;
    }

    /**
     * 20
     *  栈。左括号入，右括号出，出时不匹配则false；结束时栈为空
     */
    public boolean isValid(String s) {
        int length = s.length();
        char[] chars = s.toCharArray();
        Stack<Character> stack = new Stack();
        Map<Character, Character> map = new HashMap<>();
        map.put('}', '{');
        map.put(']', '[');
        map.put(')', '(');
        Set<Character> leftQuates = new HashSet<>(map.values());
        Set<Character> rightQuates = map.keySet();
        for (int i =0; i < length; i++) {
            char aChar = chars[i];
            if(leftQuates.contains(aChar)){
                stack.push(aChar);
            }else if(rightQuates.contains(aChar)){
                if(stack.isEmpty()){
                    return false;
                }
                Character pop = stack.pop();
                if(pop!=map.get(aChar)){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    /**
     * 155
     *  两个栈，正常栈，最小栈
     *  push时；正常栈入栈，若元素小于等于最小栈栈顶元素，入栈
     *  top；返回正常栈top
     *  pop；弹出正常栈栈顶元素，若等于最小栈栈顶元素，弹出最小栈栈顶
     *  getMin；返回最小栈栈顶
     */
    class MinStack {
        Stack<Integer> stack;
        Stack<Integer> min;
        public MinStack() {
            stack = new Stack<>();
            min = new Stack<>();
        }

        public void push(int val) {
            stack.push(val);
            if(min.isEmpty() || val<=min.peek()){
                min.push(val);
            }
        }

        public void pop() {
            if(stack.isEmpty()){
                return;
            }
            Integer pop = stack.pop();
            if(!min.isEmpty() && min.peek().equals(pop)){
                min.pop();
            }
        }

        public Integer top() {
            if(stack.isEmpty()){
                return null;
            }
            return stack.peek();
        }

        public Integer getMin() {
            if(min.isEmpty()){
                return null;
            }
            return min.peek();
        }
    }

    /**
     * 146
     *  Map放缓存；自定义双向链表保存顺序，节点包含前后元素；map2快速查询
     *  get时，从map获取
     *  put时
     *      更新map、双向链表；如何o(1)删除？
     *      超出容量，删除双向链表最后元素
     *      首次；构建Node，pre=null, next=head；赋值head、tail
     *      2次；构建Node；head.pre=node，tail.pre==null则赋值node
     *      3次；构建Node；head.pre=node。。。
     *      更新；map2定位node，
     *          是head则返回；
     *          是tail，node.pre.next=node.next, tail=node.pre；不是，node.pre.next=node.next, node.next.pre=node.pre
     *          放首位node.pre=null, node.next=head, head.pre=node, head=node
     *     移除。tail.pre.next=null, tail=tail.pre
     */
    class LRUCache {
        class Node {
            Node pre;
            Node next;
            int key;
        }
        Map<Integer, Integer> map = new HashMap<>();
        Map<Integer, Node> orderMap = new HashMap<>();
        Node head, tail;
        int capacity;
        public LRUCache(int capacity) {
            this.capacity = capacity;
        }

        public int get(int key) {
            if(map.containsKey(key)){
                // 移除当前位置，前后关联
                Node node = orderMap.get(key);
                if(node.pre!=null){
                    node.pre.next = node.next;
                    if(node.next!=null){
                        node.next.pre = node.pre;
                    }else{// 是tail
                        tail = node.pre;
                    }
                    node.next = head;
                    node.pre = null;
                    head.pre = node;
                    head = node;
                }
                return map.get(key);
            }
            return -1;
        }

        public void put(int key, int value) {
            if(!map.containsKey(key) && map.size()==capacity){
                // 移除缓存
                map.remove(tail.key);
                orderMap.remove(tail.key);
                Node pre = tail.pre;
                if(pre==null){
                    head =null;
                    tail=null;
                }else{
                    pre.next = null;
                    tail = pre;
                }
            }
            map.put(key, value);
            if(orderMap.containsKey(key)){
                // 移除当前位置，前后关联
                Node node = orderMap.get(key);
                if(node.pre!=null){
                    node.pre.next = node.next;
                    if(node.next!=null){
                        node.next.pre = node.pre;
                    }else{// 是tail
                        tail = node.pre;
                    }
                    node.next = head;
                    node.pre = null;
                    head.pre = node;
                    head = node;
                }
            }else{
                Node node = new Node();
                node.key = key;
                node.pre = null;
                node.next = head;
                if(head==null){
                    head=node;
                }else{
                    head.pre=node;
                }
                head=node;
                if(tail==null){
                    tail=node;
                }else if(tail.pre==null){
                    tail.pre = node;
                }
                orderMap.put(key, node);
            }
        }
    }

    /**
     * 491
     *  二进制枚举。or 循环新增
     *  滑动窗口
     *      是递增；修改pre，记录子序列(空时加入pre，加入num)
     *      不是；修改pre，保存非空子序列
     *  按子序列，生成结果。至少两个元素，set去重
     *      依次加入2、3、4...个元素；遍历Map生成
     *
     */
    public List<List<Integer>> findSubsequences(int[] nums) {
        int length = nums.length;
        if(length <2){
            return Collections.emptyList();
        }
//        List<List<Integer>> temp = new ArrayList<>();
//        int pre = nums[0];
//        List<Integer> tempItem = new ArrayList<>();
//        for (int i = 1; i < length; i++) {
//            int num = nums[i];
//            if(num>=pre){
//                if(tempItem.size()==0){
//                    tempItem.add(pre);
//                }
//                tempItem.add(num);
//            }else{
//                if(tempItem.size()!=0){
//                    temp.add(tempItem);
//                    tempItem = new ArrayList<>();
//                }
//            }
//            pre = num;
//        }
//        if(tempItem.size()!=0){
//            temp.add(tempItem);
//        }
        Map<String, List<Integer>> map = new TreeMap<>();
//        for(List<Integer> item : temp){
        List<Integer> item = Arrays.stream(nums)
                .boxed()
                .collect(Collectors.toList());
            // 依次加入2、3、4...个元素
            for (int i = 0; i < item.size()-1; i++) {
                for (int j = i+1; j < item.size(); j++) {
                    Integer iNum = item.get(i);
                    Integer jNum = item.get(j);
                    String key = iNum +","+ jNum;
                    if(iNum>jNum || map.containsKey(key)){
                        continue;
                    }
                    List<Integer> value = Arrays.asList(iNum, jNum);
                    Map<String, List<Integer>> tempMap = new HashMap<>();
                    tempMap.put(key, value);
                    for (int k = j+1; k < item.size(); k++) {
                        Integer kNum = item.get(k);
                        if(jNum>kNum){
                            continue;
                        }
                        Map<String, List<Integer>> tempMap2 = new HashMap<>();
                        for(Map.Entry<String, List<Integer>> entry : tempMap.entrySet()){
                            List<Integer> mapVal = entry.getValue();
                            String nKey = entry.getKey()+","+kNum;
                            if(!tempMap.containsKey(nKey) && !tempMap2.containsKey(nKey) && mapVal.get(mapVal.size()-1)<=kNum){
                                List<Integer> nValue = new ArrayList<>(mapVal);
                                nValue.add(kNum);
                                tempMap2.put(nKey, nValue);
                            }
                        }
                        tempMap.putAll(tempMap2);
                    }
                    map.putAll(tempMap);
                }
            }
//        }

        return new ArrayList<>(map.values());
    }


    @Test
    public void fast() throws Exception {
        String str1 = Files.readAllLines(Paths.get("C:\\Users\\Administrator\\Desktop\\t1"))
                .stream().collect(Collectors.joining(""));
        String str2 = Files.readAllLines(Paths.get("C:\\Users\\Administrator\\Desktop\\t2"))
                .stream().collect(Collectors.joining(""));
        List<List<Integer>> list1 = JSON.parseObject(str1, new TypeReference<List<List<Integer>>>() {});
        List<List<Integer>> list2 = JSON.parseObject(str2, new TypeReference<List<List<Integer>>>() {});
        list1.removeAll(list2);
        System.out.println(JSON.toJSONString(list1));

    }

}